#include "BalanceTree.h"

using namespace std;


int main()

{
	const double CLOCKS_PER_MILLISECOND = ((clock_t)1);
	cout << "PART 1.1:测试AVLTREE是否能实现balance功能" << endl;
	AVLTree<double> tree1;
	tree1.insert(0.5);
	tree1.insert(1);
	tree1.insert(1.5);
	tree1.insert(2);
	tree1.insert(0.0);
	cout<<tree1.contains(0.5)<<endl<<tree1.contains(10)<<endl;
	tree1.displaytree();//按递增顺序insert，测试AVLTree是否能实现balance功能。
	cout << endl << endl;
	
	///测试作业中两个函数的功能。

	///test BST_sort.
	cout << "PART 1.2:AVLTREE的BST功能测试" << endl << endl ;
	AVLTree<double> a;
	vector<double> data;
	data.push_back(0);
	data.push_back(0.5);
	data.push_back(1);
	data.push_back(1.5);
	data.push_back(2.0);
	data.push_back(2.5);
	data.push_back(3);
	data.push_back(3.5);
	data.push_back(4);
	data.push_back(4.5);
	data.push_back(5);
	data.push_back(5.5);
	data.push_back(6);

	//输出初始的_data.
	cout << "the test vector is ：   ";
	for (int i = 0; i < data.size(); i++)
	{
		cout << data[i] << "     ";
	}
	cout << endl;
	//
	clock_t startTime1, endTime1;
	startTime1 = clock();//对BST_sort的运行时间进行计时
	data = a.BST_sort(data);
	endTime1 = clock();//计时结束

	//输出由vector得到的tree。
	cout << "display of the tree is:     " ;
	a.displaytree();
	//输出覆盖后的_data.
	cout << "the final vector is:  ";
	for (int i = 0; i < data.size(); i++)
	{
		cout << data[i] << "     ";
	}
	cout <<endl<< "The run time is: " << (double)(endTime1 - startTime1)/ CLOCKS_PER_MILLISECOND << "  ms" << endl<<endl;



	///test Randomized_BST_sort.
	cout << endl << endl << "PART 1.3:AVLTREE的Randomized_BST_sort的功能测试" << endl << endl;
	AVLTree<double> b;
	vector<double> data_;
	data_.push_back(0);
	data_.push_back(0.5);
	data_.push_back(1.0);
	data_.push_back(1.5);
	data_.push_back(2.0);
	data_.push_back(2.5);
	data_.push_back(3);
	data_.push_back(3.5);
	data_.push_back(4);
	data_.push_back(4.5);
	data_.push_back(5);
	data_.push_back(5.5);
	data_.push_back(6);
	//输出初始的_data.

	cout << "the test vector is ：   ";
	for (int i = 0; i < data_.size(); i++)
	{
		cout << data_[i] << "     ";
	}
	cout << endl;
	//
	clock_t startTime2, endTime2;
	startTime2 = clock();//对Randomized_BST_sort的运行时间进行计时
	data_ = b.Randomized_BST_sort(data_);
	endTime2 = clock();
	//输出由vector得到的tree。
	cout << "display of the tree is:     " ;
	b.displaytree();

	//输出覆盖后的_data.
	cout << "the final vector is:  ";
	for (int i = 0; i < data_.size(); i++)
	{
		cout << data_[i] << "     ";
	}
	cout << endl << "The run time is: " << (double)(endTime2 - startTime2) / CLOCKS_PER_MILLISECOND << "  ms" << endl << endl;
	cout << endl<<endl;




	cout << "PART 2.1:测试SPLAYTREE是否能实现splay功能" << endl << endl;
	splayTree<double> tree2;
	tree2.insert(1.5);
	tree2.insert(2.0);
	tree2.insert(0.5);
	tree2.insert(1.0);
	tree2.insert(0.0);
	//tree2.printTree();
	//cout << endl << endl;
	cout << "初始状态的tree为：   ";
	tree2.displaytree();//查看访问之前的tree2
	cout<<"访问0.5的结果："<<tree2.contains(0.5)<<endl<<"访问0.5之后的tree为：  ";
	tree2.displaytree();//查看访问0.5之后的tree2.测试是否实现了splay功能。
	cout << "访问1.5的结果为： "<<tree2.contains(1.5) <<  endl<<"访问1.5之后的tree变为：  ";
	tree2.displaytree();//访问1.5，变回原状

	/////
	///测试作业中两个函数的功能。

	///test BST_sort.
	cout << "PART 2.2:SPLAYTREE的BST功能测试" << endl << endl;
	splayTree<double> as;
	vector<double> datas;
	datas.push_back(0);
	datas.push_back(0.5);
	datas.push_back(1);
	datas.push_back(1.5);
	datas.push_back(2.0);
	datas.push_back(2.5);
	datas.push_back(3);
	datas.push_back(3.5);
	datas.push_back(4);
	datas.push_back(4.5);
	datas.push_back(5);
	datas.push_back(5.5);
	datas.push_back(6);

	//输出初始的_data.
	cout << "the test vector is ：   ";
	for (int i = 0; i < datas.size(); i++)
	{
		cout << datas[i] << "     ";
	}
	cout << endl;
	//
	clock_t startTime1s, endTime1s;
	startTime1s = clock();//对BST_sort的运行时间进行计时
	datas = as.BST_sort(datas);
	endTime1s = clock();//计时结束

	//输出由vector得到的tree。
	cout << "display of the tree is:     ";
	as.displaytree();
	//输出覆盖后的_data.
	cout << "the final vector is:  ";
	for (int i = 0; i < datas.size(); i++)
	{
		cout << datas[i] << "     ";
	}
	cout << endl << "The run time is: " << (double)(endTime1s - startTime1s) / CLOCKS_PER_MILLISECOND << "  ms" << endl << endl;



	///test Randomized_BST_sort.
	cout << endl << endl << "PART 2.3:SPLAYTREE的Randomized_BST_sort的功能测试" << endl << endl;
	splayTree<double> bs;
	vector<double> data_s;
	data_s.push_back(0);
	data_s.push_back(0.5);
	data_s.push_back(1.0);
	data_s.push_back(1.5);
	data_s.push_back(2.0);
	data_s.push_back(2.5);
	data_s.push_back(3);
	data_s.push_back(3.5);
	data_s.push_back(4);
	data_s.push_back(4.5);
	data_s.push_back(5);
	data_s.push_back(5.5);
	data_s.push_back(6);
	//输出初始的_data.

	cout << "the test vector is ：   ";
	for (int i = 0; i < data_s.size(); i++)
	{
		cout << data_s[i] << "     ";
	}
	cout << endl;
	//
	clock_t startTime2s, endTime2s;
	startTime2s = clock();//对Randomized_BST_sort的运行时间进行计时
	data_s = bs.Randomized_BST_sort(data_s);
	endTime2s = clock();
	//输出由vector得到的tree。
	cout << "display of the tree is:     ";
	bs.displaytree();

	//输出覆盖后的_data.
	cout << "the final vector is:  ";
	for (int i = 0; i < data_s.size(); i++)
	{
		cout << data_s[i] << "     ";
	}
	cout << endl << "The run time is: " << (double)(endTime2s - startTime2s) / CLOCKS_PER_MILLISECOND << "  ms" << endl << endl;
}
